#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

void floyd(vector<vector<int>>& graph, int n) {
    vector<vector<int>> dist(n, vector<int>(n));
    vector<vector<int>> path(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
            if (graph[i][j] != INF && i != j) {
                path[i][j] = i;
            } else {
                path[i][j] = -1;
            }
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j];
                }
            }
        }
    }

    cout << "最短路径：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && dist[i][j] != INF) {
                cout << i << " -> " << j << " 的最短路径为：" << i;
                int p = path[i][j];
                while (p != j) {
                    cout << " -> " << p;
                    p = path[p][j];
                }
                cout << " -> " << j << ", 距离为：" << dist[i][j] << endl;
            }
        }
    }
}

int main() {
    int n; 
    cout << "请输入点的数量：";
    cin >> n;

    vector<vector<int>> graph(n, vector<int>(n));

    cout << "请依次输入各个点之间的距离(使用INF表示无穷大):" << endl;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    floyd(graph, n);

    return 0;
}